package DataStructure.hash.swordOffer;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 剑指 Offer 50. 第一个只出现一次的字符 https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
 * 题目简述：在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
 */
public class FirstUniqChar {

    /**
     * 思路一：有序哈希表。使用一个添加顺序的LinkedHashMap遍历添加记录字符个数，然后再遍历LinkedHashMap查找为个数为1的字符
     */
    public char firstUniqChar(String s) {
        //默认是按添加顺序排序
        LinkedHashMap<Character, Integer> linkedHashMap = new LinkedHashMap<>();
        for (int i = 0;i < s.length();i++) {
            //添加顺序：key在被初次添加时会将其链接到双向链表尾部，否则直接更新节点值
            linkedHashMap.put(s.charAt(i), linkedHashMap.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (Map.Entry<Character, Integer> entry : linkedHashMap.entrySet()) {
            if (entry.getValue() == 1) return entry.getKey();
        }
        return ' ';
    }

    /**
     * 思路二：字母表。先遍历一遍字符串用字母表记录每个字符的个数，再遍历一遍查找为个数为1的字符
     */
    public char firstUniqChar2(String s) {
        int[] table = new int[26];
        for (int i = 0;i < s.length();i++) {
            table[s.charAt(i) - 'a']++;
        }
        for (int i = 0;i < s.length();i++) {
            if (table[s.charAt(i) - 'a'] == 1) return s.charAt(i);
        }
        return ' ';
    }
}
